package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 从降序数组中组合小于等于目标数的最大值的解决方案
 * <p>
 * 问题描述：
 * 给定一个降序排列的数组和一个目标数，从数组中选择数字组合成一个最大的数，
 * 要求这个数小于等于目标数。如果无法组合出这样的数，则返回-1。
 *
 * @author Your Name
 * @date 2024/01/20
 */
public class MaxNumberFromArray {

    /**
     * 解法1：迭代法 - 从高位到低位逐位处理
     * <p>
     * 算法复杂度：
     * - 时间复杂度：O(n + m)，其中n为数组长度，m为目标数字的位数
     * - 空间复杂度：O(m)，其中m为目标数字的位数
     * <p>
     * 核心思路：
     * 1. 将目标数字转换为字符数组，方便按位比较
     * 2. 从高位到低位处理每一位：
     * - 尽可能选择小于等于当前位的最大数字
     * - 一旦选择了小于当前位的数字，后续位可以直接选择最大数字
     * 3. 如果某位无法找到合适的数字，需要回退并调整策略
     *
     * @param arr 降序排列的数组，例如[9,8,7,6,5]
     * @param n   目标数字，例如8754
     * @return 返回可以组合出的小于等于n的最大值，如果无法组合则返回-1
     */
    public static long findMaxLessOrEqual(int[] arr, long n) {
        // 1. 输入验证：检查数组是否为空或null
        if (arr == null || arr.length == 0) {
            return -1;
        }

        // 2. 数据预处理：将目标数字转换为字符数组以便按位处理
        String nStr = String.valueOf(n); // 将数字转换为字符串
        char[] nChars = nStr.toCharArray(); // 转换为字符数组
        int targetLen = nChars.length; // 获取目标数字的位数

        // 3. 特殊情况处理：检查是否存在可能的解
        if (arr[arr.length - 1] > (nChars[0] - '0')) { // 数组最小值比首位还大
            return -1;
        }

        // 4. 初始化结果构建器和状态标记
        StringBuilder result = new StringBuilder(); // 用于构建结果数字
        boolean hasSmaller = false; // 标记是否已选择过小于当前位的数字

        // 5. 从高位到低位逐位处理
        for (int i = 0; i < targetLen; i++) {
            int currentDigit = nChars[i] - '0'; // 获取当前位的数字值

            if (hasSmaller) {
                // 5.1 如果已经选择了更小的数字，后续位直接选择最大值
                result.append(arr[0]);
                continue;
            }

            // 5.2 查找小于等于当前位的最大数字
            int maxLessOrEqual = findMaxLessOrEqualDigit(arr, currentDigit);

            if (maxLessOrEqual == -1) {
                // 5.3 处理当前位无法找到合适数字的情况
                if (result.length() == 0) { // 如果是第一位就失败
                    return -1;
                }
                // 需要回退一位并选择更小的数字
                if (!handleBacktracking(arr, result, targetLen)) {
                    return -1; // 回退失败
                }
                break; // 回退成功后结束循环
            } else {
                // 5.4 找到合适的数字，更新结果
                result.append(maxLessOrEqual);
                if (maxLessOrEqual < currentDigit) { // 更新状态标记
                    hasSmaller = true;
                }
            }
        }

        // 6. 转换并返回最终结果
        return Long.parseLong(result.toString());
    }

    /**
     * 辅助方法：在数组中查找小于等于目标数字的最大数
     *
     * @param arr    降序排列的数组
     * @param target 目标数字
     * @return 返回找到的数字，如果没找到返回-1
     */
    private static int findMaxLessOrEqualDigit(int[] arr, int target) {
        for (int num : arr) {
            if (num <= target) {
                return num;
            }
        }
        return -1;
    }

    /**
     * 辅助方法：处理需要回退的情况
     *
     * @param arr       降序排列的数组
     * @param result    当前结果构建器
     * @param targetLen 目标长度
     * @return 回退是否成功
     */
    private static boolean handleBacktracking(int[] arr, StringBuilder result, int targetLen) {
        // 1. 获取最后一位数字
        int lastDigit = result.charAt(result.length() - 1) - '0';
        result.setLength(result.length() - 1); // 删除最后一位

        // 2. 查找小于最后一位的最大数字
        boolean found = false;
        for (int num : arr) {
            if (num < lastDigit) {
                result.append(num);
                found = true;
                break;
            }
        }

        // 3. 如果找到了合适的数字，用最大数字填充剩余位置
        if (found) {
            while (result.length() < targetLen) {
                result.append(arr[0]);
            }
            return true;
        }

        return false;
    }

    /**
     * 解法2：贪心算法 - 逐位选择最优解
     * <p>
     * 算法复杂度：
     * - 时间复杂度：O(n * m)，其中n为数组长度，m为目标数字的位数
     * - 空间复杂度：O(m)，其中m为目标数字的位数
     * <p>
     * 核心思路：
     * 1. 从高位到低位，每一位都尽可能选择小于等于目标数对应位的最大数字
     * 2. 如果某一位选择了小于目标数对应位的数字，后面的位都可以选择最大的数字
     * 3. 如果某一位无法找到合适的数字，则需要回退到上一位选择更小的数字
     *
     * @param arr 降序排列的数组
     * @param n   目标数字
     * @return 返回可以组合出的小于等于n的最大值，如果无法组合则返回-1
     */
    public static long findMaxLessOrEqualGreedy(int[] arr, long n) {
        // 1. 输入验证
        if (arr == null || arr.length == 0) {
            return -1;
        }

        // 2. 初始化数据
        String nStr = String.valueOf(n); // 将目标数转换为字符串
        StringBuilder result = new StringBuilder(); // 用于构建结果
        boolean hasSmaller = false; // 标记是否已选择更小的数字

        // 3. 从高位到低位处理每一位
        for (int i = 0; i < nStr.length(); i++) {
            int currentDigit = nStr.charAt(i) - '0'; // 获取当前位的数字

            if (hasSmaller) {
                // 3.1 如果已选择更小的数字，后续位直接选最大值
                result.append(arr[0]);
                continue;
            }

            // 3.2 查找小于等于当前位的最大数字
            int maxLessOrEqual = -1;
            for (int num : arr) {
                if (num <= currentDigit) {
                    maxLessOrEqual = num;
                    break;
                }
            }

            // 3.3 处理无法找到合适数字的情况
            if (maxLessOrEqual == -1) {
                if (result.length() == 0) { // 如果是第一位就失败
                    return -1;
                }
                // 需要回退到更小的数：构建新的目标数并递归
                StringBuilder zeros = new StringBuilder();
                for (int j = 0; j < nStr.length() - result.length(); j++) {
                    zeros.append('0'); // 补充后续位为0
                }
                // 递归查找小于当前数的最大值
                return findMaxLessOrEqualGreedy(arr,
                        Long.parseLong(result.toString() + zeros) - 1);
            }

            // 3.4 找到合适的数字，更新结果
            result.append(maxLessOrEqual);
            if (maxLessOrEqual < currentDigit) { // 更新状态标记
                hasSmaller = true;
            }
        }

        // 4. 返回最终结果
        return Long.parseLong(result.toString());
    }

    /**
     * 解法3：回溯算法 - 穷举所有可能的组合
     * <p>
     * 算法复杂度：
     * - 时间复杂度：O(n^m)，其中n为数组长度，m为目标数字的位数
     * - 空间复杂度：O(m)，递归调用栈的深度
     * <p>
     * 核心思路：
     * 1. 使用递归回溯，尝试所有可能的数字组合
     * 2. 剪枝条件：
     * - 如果当前数字大于目标位对应的数字，直接跳过（利用数组降序特性）
     * - 一旦选择了小于目标位的数字，后续位置可以直接选择最大数字
     * 3. 记录过程中找到的最大值
     * 
     * 举例说明：
     * 假设数组为[9,5,2]，目标数为538
     * 1. 第一位可选数字：5,2（9>5，跳过）
     * 2. 选择5后，第二位可选数字：9,5,2（都≤3）
     * 3. 选择3后，第三位可选数字：9,5,2（都≤8）
     * 4. 最终可能的解：528, 525, 522, 298, 295, 292, 258, 255, 252, ...
     * 5. 其中最大的解为528
     *
     * @param arr 降序排列的数组
     * @param n   目标数字
     * @return 返回可以组合出的小于等于n的最大值，如果无法组合则返回-1
     */
    public static long findMaxLessOrEqualBacktrack(int[] arr, long n) {
        // 1. 输入验证：检查边界情况
        if (arr == null || arr.length == 0) {
            return -1;
        }

        // 2. 初始化数据
        String targetNumStr = String.valueOf(n); // 将目标数转换为字符串，便于按位比较
        long[] bestResult = { -1 }; // 使用数组存储最佳结果，便于在递归中修改
        StringBuilder currentNum = new StringBuilder(); // 用于构建当前尝试的数字

        // 3. 开始回溯搜索过程
        findBestNumber(arr, targetNumStr, currentNum, 0, false, bestResult);

        // 4. 返回找到的最大值
        return bestResult[0];
    }

    /**
     * 回溯算法的核心实现 - 寻找最佳数字组合
     * 
     * 该方法通过递归方式，从高位到低位逐步构建可能的数字组合，并记录满足条件的最大值。
     * 整个过程可以想象成一棵决策树，每一层代表一个数位，每个节点的分支代表可以选择的数字。
     *
     * @param digits       降序排列的数字数组，例如[9,5,2]
     * @param targetNumStr 目标数字的字符串表示，例如"538"
     * @param currentNum   当前正在构建的数字，例如"5"
     * @param digitPos     当前处理的位置（从0开始），例如1表示处理第二位
     * @param canUseAny    是否可以使用任意数字（当已选择的数字小于目标数对应位时为true）
     * @param bestResult   用于存储找到的最佳结果
     */
    private static void findBestNumber(int[] digits, String targetNumStr, StringBuilder currentNum,
            int digitPos, boolean canUseAny, long[] bestResult) {
        // 1. 终止条件：已经处理完所有位置（构建了完整的数字）
        if (digitPos == targetNumStr.length()) {
            // 将构建好的字符串转换为数字
            long constructedNum = Long.parseLong(currentNum.toString());
            long targetNum = Long.parseLong(targetNumStr);

            // 验证构建的数字是否满足条件（小于等于目标数）
            if (constructedNum <= targetNum) {
                // 更新最佳结果（取较大值）
                bestResult[0] = Math.max(bestResult[0], constructedNum);
            }
            return; // 结束当前递归分支
        }

        // 2. 获取目标数字当前位的数值
        int targetDigit = targetNumStr.charAt(digitPos) - '0';

        // 3. 特殊情况处理：如果之前已选择了小于目标数对应位的数字
        if (canUseAny) {
            // 此时可以直接使用最大的数字（数组中的第一个元素）
            // 因为数组已按降序排列，所以digits[0]是最大的数字
            currentNum.append(digits[0]);

            // 递归处理下一位，canUseAny保持为true
            findBestNumber(digits, targetNumStr, currentNum, digitPos + 1, true, bestResult);

            // 回溯：恢复状态，删除刚才添加的数字
            currentNum.setLength(currentNum.length() - 1);
            return; // 不需要尝试其他数字，直接返回
        }

        // 4. 常规情况：尝试所有可能的数字
        for (int digit : digits) {
            // 剪枝优化：如果当前数字大于目标位的数字，则跳过
            // 因为数组降序排列，所以一旦发现大于目标位的数字，后续就不需要再尝试了
            if (digit > targetDigit) {
                continue;
            }

            // 将当前数字添加到构建中的数字串
            currentNum.append(digit);

            // 递归处理下一位
            // 如果当前数字小于目标位的数字，则后续可以使用任意数字（canUseAny=true）
            // 否则需要继续比较下一位（canUseAny=false）
            findBestNumber(digits, targetNumStr, currentNum, digitPos + 1,
                    digit < targetDigit, bestResult);

            // 回溯：恢复状态，删除刚才添加的数字，尝试下一个可能的数字
            currentNum.setLength(currentNum.length() - 1);
        }
    }

    /**
     * 主方法：用于测试各种实现方法的效果
     * 包含三个测试用例：
     * 1. 基本情况：测试正常输入下的算法表现
     * 2. 需要回退的情况：测试算法在需要回退时的处理能力
     * 3. 无法组合的情况：测试算法对特殊情况的处理
     */
    public static void main(String[] args) {
        // 测试用例1：基本情况 - 测试算法在正常输入下的表现
        // 预期结果：应该能找到一个有效的解
        int[] arr1 = { 9, 4, 3, 2 }; // 降序排列的数组
        long n1 = 433211; // 目标数字
     System.out.println("测试用例1：");
        System.out.println("数组：" + Arrays.toString(arr1));
        System.out.println("目标数：" + n1);
        System.out.println("解法1结果：" + findMaxLessOrEqual(arr1, n1));
        System.out.println("解法2结果：" + findMaxLessOrEqualGreedy(arr1, n1));
        System.out.println("解法3结果：" + findMaxLessOrEqualBacktrack(arr1, n1));

        // 测试用例2：需要回退的情况 - 测试算法的回退处理能力
        // 预期结果：算法需要在某些位置进行回退才能找到最优解
        int[] arr2 = { 9, 8, 7, 6, 5 }; // 降序排列的数组
        long n2 = 8754; // 目标数字
        System.out.println("\n测试用例2：");
        System.out.println("数组：" + Arrays.toString(arr2));
        System.out.println("目标数：" + n2);
        System.out.println("解法1结果：" + findMaxLessOrEqual(arr2, n2));
        System.out.println("解法2结果：" + findMaxLessOrEqualGreedy(arr2, n2));
        System.out.println("解法3结果：" + findMaxLessOrEqualBacktrack(arr2, n2));

        // 测试用例3：无法组合的情况 - 测试算法对特殊情况的处理
        // 预期结果：由于数组中的数字都太大，应该返回-1表示无法组合
        int[] arr3 = { 9, 8, 7 }; // 降序排列的数组
        long n3 = 500; // 目标数字
        System.out.println("\n测试用例3：");
        System.out.println("数组：" + Arrays.toString(arr3));
        System.out.println("目标数：" + n3);
        System.out.println("解法1结果：" + findMaxLessOrEqual(arr3, n3));
        System.out.println("解法2结果：" + findMaxLessOrEqualGreedy(arr3, n3));
        System.out.println("解法3结果：" + findMaxLessOrEqualBacktrack(arr3, n3));
    }
}